﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0137_TopKFrequent : IAlgorithm
    {
        // 前 K 个高频元素

        // 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

        // 提示：
        //  1 <= nums.length <= 10^5
        //  k 的取值范围是[1, 数组中不相同的元素的个数]
        //  题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

        // 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 3, 3, 1, 2, 2, 3 };
            var k = 2;
            // 算法执行与打印
            var res = TopKFrequent(nums, k);
            foreach (var item in res)
                Console.Write(item + " ");
        }

        // 算法
        public int[] TopKFrequent(int[] nums, int k)
        {
            var map = new Dictionary<int, int>();
            foreach (var num in nums)
                if (!map.ContainsKey(num))
                    map.Add(num, 0);
                else
                    map[num]++;

            var tempLst = map.OrderByDescending(x=>x.Value).Select(x=>x.Key).ToList();
            int[] res = new int[k];
            for (int i = 0; i < k; i++)
                res[i] = tempLst[i];
            return res;
        }
    }
}
